package site.wanjiahao;

import java.nio.file.Watchable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

public class Main {

    public static void main(String[] args) {
        knapsack();
    }

    // 最优装载问题
    static void pirate() {
        // 装下最多货物，所以是每次装载最小的
        int w = 30;
        int[] subject = {3, 5, 4, 10, 7, 14, 2, 11};
        Arrays.sort(subject);
        int count = 0;
        for (int j : subject) {
            if (j <= w) {
                w -= j;
                count++;
            }
        }
        System.out.println("最多能装载" + count + "件物品");
    }

    // 零钱兑换问题。贪心选择只能是局部最优解，但是整体未必是最优解。
    static void coinChange() {
        // 使用最小的钱币数量，兑换钱
        int count = 41;
        int[] coin = {25, 10, 5, 1};
        // 存放兑换当前铅笔，所需要的面值和数量
        HashMap<Integer, Integer> coins = new HashMap<>();
        // 每次选择最大的钱币兑换
        Arrays.sort(coin);
        for (int i = coin.length - 1; i >= 0; i--) {
            if (coin[i] > count) {
                // 不可以兑换
                continue;
            }
            int num = 0;
            // 可以兑换
            while (count >= coin[i]) {
                coins.put(coin[i], ++num);
                count -= coin[i];
            }
        }
        coins.forEach((key, value) -> {
            System.out.println("面额：" + key + "需要" + value + "张钱币");
        });
    }

    // 0-1背包问题， 使用贪心算法，可得价值最大优先，重量最小优先，性价比最高优先
    static void knapsack() {
        Comparator<Knapsack> comparator1 = (o1, o2) -> o2.value - o1.value;
        Comparator<Knapsack> comparator2 = (o1, o2) -> o1.weight - o2.value;
        Comparator<Knapsack> comparator3 = (o1, o2) -> o2.valueDensity.compareTo(o1.valueDensity);
        int capacity = 150;
        Knapsack[] knapsacks = {
                new Knapsack(35, 10),
                new Knapsack(30, 40),
                new Knapsack(60, 30),
                new Knapsack(50, 50),
                new Knapsack(40, 35),
                new Knapsack(10, 40),
                new Knapsack(25, 30),
        };

        sort(capacity, knapsacks, comparator1);
        System.out.println("-----------------");
        sort(capacity, knapsacks, comparator2);
        System.out.println("-----------------");
        sort(capacity, knapsacks, comparator3);
    }

    static void sort(int capacity, Knapsack[] knapsacks, Comparator<Knapsack> comparator) {
        Arrays.sort(knapsacks, comparator);
        ArrayList<Knapsack> list = new ArrayList<>();
        int totalValue = 0;
        for (Knapsack value : knapsacks) {
            // 当前不能放下
            if (value.weight > capacity) {
                continue;
            }
            // 可以放下
            list.add(value);
            totalValue += value.value;
            capacity -= value.weight;
        }

        for (Knapsack knapsack : list) {
            System.out.println("选择重量为: " + knapsack.weight + "价值为：" + knapsack.value);
        }
        System.out.println("总价值为: " + totalValue);
    }

    // 背包对象
    static class Knapsack {

        int weight;

        int value;

        Double valueDensity;

        public Knapsack(int weight, int value) {
            this.weight = weight;
            this.value = value;
            this.valueDensity = value * 1.0 / weight;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Knapsack{");
            sb.append("weight=").append(weight);
            sb.append(", value=").append(value);
            sb.append(", valueDensity=").append(valueDensity);
            sb.append('}');
            return sb.toString();
        }
    }

}
